/*********************************************************************************
 * 
 * MIT License
 *
 * Copyright (c) 2023 shaoguangcn
 * 
 * Permission is hereby granted, free of charge, to any person obtaining a copy
 * of this software and associated documentation files (the "Software"), to deal
 * in the Software without restriction, including without limitation the rights
 * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
 * copies of the Software, and to permit persons to whom the Software is
 * furnished to do so, subject to the following conditions:
 * 
 * The above copyright notice and this permission notice shall be included in all
 * copies or substantial portions of the Software.
 * 
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
 * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
 * SOFTWARE.
 * 
 *********************************************************************************/

/**
 * \file floating_to_chars.cpp
 */

#include <cmath>
#include <cstring>
#include <limits>
#include <climits>

#include "charconv.hpp"

namespace detail {

namespace ryu {

// A floating decimal representing m * 10^e.
struct floating_decimal_32
{
    uint32_t mantissa;
    // Decimal exponent's range is -45 to 38 inclusive, and can fit in a short if needed.
    int32_t exponent;
    bool sign;
};

struct floating_decimal_64
{
    uint64_t mantissa;
    // Decimal exponent's range is -324 to 308 inclusive, and can fit in a short if needed.
    int32_t exponent;
    bool sign;
};

} // namespace ryu

// A traits class that contains pertinent information about the binary
// format of each of the floating-point types we support.
template<typename T>
struct floating_type_traits {};

template<>
struct floating_type_traits<float>
{
    static constexpr int mantissa_bits = std::numeric_limits<float>::digits;
    static constexpr int exponent_bits = sizeof(float) * CHAR_BIT - std::numeric_limits<float>::digits;
    static constexpr bool has_implicit_leading_bit = true;
    using mantissa_t = uint32_t;
    using shortest_scientific_t = ryu::floating_decimal_32;

    static constexpr uint64_t pow10_adjustment_tab[] = {
        0b0000000000011101011100110101100101101110000000000000000000000000
    };
};

template<>
struct floating_type_traits<double>
{
    static constexpr int mantissa_bits = std::numeric_limits<double>::digits;
    static constexpr int exponent_bits = sizeof(double) * CHAR_BIT - std::numeric_limits<double>::digits;
    static constexpr bool has_implicit_leading_bit = true;
    using mantissa_t = uint64_t;
    using shortest_scientific_t = ryu::floating_decimal_64;

    static constexpr uint64_t pow10_adjustment_tab[] = {
        0b0000000000000000000000011000110101110111000001100101110000111100,
        0b0111100011110101011000011110000000110110010101011000001110011111,
        0b0101101100000000011100100100111100110110110100010001010101110000,
        0b0011110010111000101111110101100011101100010001010000000101100111,
        0b0001010000011001011100100001010000010101101000001101000000000000
    };
};

template<>
struct floating_type_traits<long double> : floating_type_traits<double> { };

// 0 or inf or nan
// returns -1 if value is normal
// returns 0 if value is subnormal
template<typename T>
int calculate_expected_output_length_special_value(const T value, const chars_format fmt, const int precision)
{
    const char* str = nullptr;
    switch (std::fpclassify(value))
    {
    case FP_INFINITE:
        str = "-inf";
        break;
    case FP_NAN:
        str = "-nan";
        break;
    case FP_ZERO:
        break;
    case FP_SUBNORMAL:
        return 0;
    CHARCONV_CPP_ATTR_LIKELY case FP_NORMAL:
        return -1;
        break;
    default:
        return 0;
        break;
    }

    if (str) {
        if (!std::signbit(value)) { // value is +-inf or +-nan
            str++;
        }
        return std::strlen(str);
    }

    // value is 0
    const bool sign = std::signbit(value);
    int expected_output_length = sign + 1;
    switch (fmt)
    {
    case chars_format::fixed:
    case chars_format::scientific:
    case chars_format::hex:
    {
        expected_output_length = sign + 1;
        if (precision) {
            expected_output_length += std::strlen(".") + precision;
        }
        if (fmt == chars_format::scientific) {
            expected_output_length += std::strlen("e+00");
        }
        else if (fmt == chars_format::hex) {
            expected_output_length += std::strlen("p+0");
        }
        return expected_output_length;
    }
    case chars_format::general:
    default: // case chars_format{}:
        break;
    }

    return expected_output_length;
}

// This subroutine of floating_to_chars_* handles writing nan, inf and 0 in
// all formatting modes.
template<typename T>
to_chars_result handle_special_value(char* first, char* const last, const T value, 
    const chars_format fmt, const int precision)
{
    const char* str = nullptr;
    switch (std::fpclassify(value))
    {
    case FP_INFINITE:
        str = "-inf";
        break;
    case FP_NAN:
        str = "-nan";
        break;
    case FP_ZERO:
        break;
    case FP_SUBNORMAL:
    CHARCONV_CPP_ATTR_LIKELY case FP_NORMAL:
        return { nullptr, std::errc{} };
        break;
    default:
        return { nullptr, std::errc{} };
        break;
    }

    if (str) {
        if (!std::signbit(value)) { // We're formatting +-inf or +-nan.
            str++; // remove '-'
        }
        const auto len = std::strlen(str);
        if (last - first < (int)len) {
            return { last, std::errc::value_too_large };
        }
        std::memcpy(first, str, len);
        first += len;
        return { first, std::errc{} };
    }

    // We're formatting 0.
    const auto origin_fisrt = first;
    const bool sign = std::signbit(value);
    int expected_output_length;
    switch (fmt)
    {
    case chars_format::fixed:
    case chars_format::scientific:
    case chars_format::hex:
    {
        expected_output_length = sign + 1;
        if (precision) {
            expected_output_length += std::strlen(".") + precision;
        }

        if (fmt == chars_format::scientific) {
            expected_output_length += std::strlen("e+00");
        }
        else if (fmt == chars_format::hex) {
            expected_output_length += std::strlen("p+0");
        }

        if (last - first < expected_output_length) {
            return {last, std::errc::value_too_large};
        }

        if (sign) {
            *first++ = '-';
        }
        *first++ = '0';

        if (precision) {
            *first++ = '.';
            std::memset(first, '0', precision);
        }

        if (fmt == chars_format::scientific) {
	        std::memcpy(first, "e+00", 4);
            first += 4;
        }
        else if (fmt == chars_format::hex) {
            std::memcpy(first, "p+0", 3);
            first += 3;
        }
    }
        break;
    case chars_format::general:
    default: // case chars_format{}:
    {
        expected_output_length = sign + 1;
        if (last - first < expected_output_length) {
            return {last, std::errc::value_too_large};
        }
        if (sign) {
            *first++ = '-';
        }
        *first++ = '0';
    }
        break;
    }

    return { first, std::errc{} };
}

// An IEEE-style decomposition of a floating-point value of type T.
template<typename T>
struct ieee_t
{
    typename floating_type_traits<T>::mantissa_t mantissa;
    uint32_t biased_exponent;
    bool sign;
};

// Decompose the floating-point value into its IEEE components.
template<typename T>
ieee_t<T> get_ieee_repr(const T value)
{
    using mantissa_t = typename floating_type_traits<T>::mantissa_t;
    constexpr int mantissa_bits = floating_type_traits<T>::mantissa_bits;
    constexpr int exponent_bits = floating_type_traits<T>::exponent_bits;
    constexpr int total_bits = mantissa_bits + exponent_bits + 1;

    constexpr auto get_uint_t = [] {
        if CXX_IF_CONSTEXPR (total_bits <= 32) {
            return uint32_t{};
        }
        else {
            return uint64_t{};
        }
    };
    using uint_t = decltype(get_uint_t());
    uint_t value_bits = 0;
    std::memcpy(&value_bits, &value, sizeof(value));

    ieee_t<T> ieee_repr;
    ieee_repr.mantissa = static_cast<mantissa_t>(value_bits & ((uint_t{1} << mantissa_bits) - 1u));
    value_bits >>= mantissa_bits;
    ieee_repr.biased_exponent = static_cast<uint32_t>(value_bits & ((uint_t{1} << exponent_bits) - 1u));
    value_bits >>= exponent_bits;
    ieee_repr.sign = (value_bits & 1) != 0;
    return ieee_repr;
}

template<typename T>
to_chars_result floating_to_chars_hex(char* first, char* const last, const T value, int precision)
{
    if (precision < 0) CHARCONV_CPP_ATTR_UNLIKELY {
        return floating_to_chars_hex(first, last, value, 0);
    }

    constexpr int mantissa_bits = floating_type_traits<T>::mantissa_bits;
    constexpr bool has_implicit_leading_bit = floating_type_traits<T>::has_implicit_leading_bit;
    constexpr int exponent_bits = floating_type_traits<T>::exponent_bits;
    constexpr int exponent_bias = (1u << (exponent_bits - 1)) - 1;
    using mantissa_t = typename floating_type_traits<T>::mantissa_t;
    constexpr int mantissa_t_width = sizeof(mantissa_t) * __CHAR_BIT__;

    to_chars_result result_tmp = handle_special_value(first, last, value, chars_format::hex, 0);
    if (result_tmp.ptr != nullptr) {
        return result_tmp;
    }

    const ieee_t<T> ieee = get_ieee_repr(value);
    const bool is_normal_number = (ieee.biased_exponent != 0);

    int32_t unbiased_exponent = (is_normal_number
				 ? ieee.biased_exponent - exponent_bias
				 : 1 - exponent_bias);

    constexpr unsigned rounded_mantissa_bits = (mantissa_bits + 3) / 4 * 4;
    static_assert(mantissa_t_width >= rounded_mantissa_bits);
    mantissa_t effective_mantissa = ieee.mantissa << (rounded_mantissa_bits - mantissa_bits);

    if (is_normal_number) {
        if CXX_IF_CONSTEXPR (has_implicit_leading_bit) {
            effective_mantissa |= mantissa_t{1} << rounded_mantissa_bits;
        }
        else {
            CHARCONV_ASSERT(effective_mantissa & (mantissa_t{1} << (mantissa_bits - 1u)));
        }
    }
    else if (precision == 0 && effective_mantissa) {
        int width = bit_width(effective_mantissa);
        int shift = rounded_mantissa_bits - width + has_implicit_leading_bit;
        unbiased_exponent -= shift;
        effective_mantissa <<= shift;
    }

    constexpr int full_hex_precision = (has_implicit_leading_bit
					? (mantissa_bits + 3) / 4
					: (mantissa_bits - 4 + 3) / 4);
    const int trailing_zeros = countr_zero(effective_mantissa) / 4;
    const int shortest_full_precision = full_hex_precision - trailing_zeros;
    CHARCONV_ASSERT(shortest_full_precision >= 0);

    int written_exponent = unbiased_exponent;
    int effective_precision = (precision != 0)  ? precision : shortest_full_precision;
    int excess_precision = 0;

    if (effective_precision < shortest_full_precision) {
      	using bitvec = mantissa_t;
        const bitvec round_bit = effective_mantissa << 1;
        const bitvec has_tail_bits = round_bit - 1;
        const bitvec lsb_bit = effective_mantissa;
        const bitvec should_round = round_bit & (has_tail_bits | lsb_bit);
        
        const int dropped_bits = 4 * (full_hex_precision - effective_precision);
        effective_mantissa >>= dropped_bits;
        effective_mantissa <<= dropped_bits;

        if (should_round & (mantissa_t{1} << dropped_bits)) {
            effective_mantissa += mantissa_t{1} << dropped_bits;

            if CXX_IF_CONSTEXPR (!has_implicit_leading_bit) {
                static_assert(mantissa_t_width == 64 && rounded_mantissa_bits == 64);
                if (effective_mantissa == 0) {
                    effective_mantissa = mantissa_t{1} << (rounded_mantissa_bits - 4);
                    written_exponent += 4;
                }
            }
        }
    }
    else {
       	excess_precision = effective_precision - shortest_full_precision;
	    effective_precision = shortest_full_precision; 
    }

    char leading_hexit;

    if CXX_IF_CONSTEXPR (has_implicit_leading_bit) {
        const auto nibble = unsigned(effective_mantissa >> rounded_mantissa_bits);
        CHARCONV_ASSERT(nibble <= 2);
        leading_hexit = '0' + nibble;
        effective_mantissa &= ~(mantissa_t{0b11} << rounded_mantissa_bits);
    } 
    else {
        const auto nibble = unsigned(effective_mantissa >> (rounded_mantissa_bits-4));
        CHARCONV_ASSERT(nibble < 16);
        leading_hexit = "0123456789abcdef"[nibble];
        effective_mantissa &= ~(mantissa_t{0b1111} << (rounded_mantissa_bits-4));
        written_exponent -= 3;
    }

    int expected_output_length = ieee.sign + 1;
    if (effective_precision + excess_precision > 0) {
        expected_output_length += std::strlen(".");
    }
    expected_output_length += effective_precision;
    const int abs_written_exponent = std::abs(written_exponent);
    expected_output_length += (abs_written_exponent >= 10000 ? std::strlen("p+ddddd")
			       : abs_written_exponent >= 1000 ? std::strlen("p+dddd")
			       : abs_written_exponent >= 100 ? std::strlen("p+ddd")
			       : abs_written_exponent >= 10 ? std::strlen("p+dd")
			       : std::strlen("p+d"));

    if (last - first < expected_output_length || 
        last - first - expected_output_length < excess_precision) {
        return { last, std::errc::value_too_large };
    }

    char* const expected_output_end = first + expected_output_length + excess_precision;
    if (ieee.sign) {
        *first++ = '-';
    }
    *first++ = leading_hexit;

    if (effective_precision + excess_precision > 0) {
        *first++ = '.';
    }

    if (effective_precision > 0) {
        int written_hexits = 0;
        int nibble_offset = rounded_mantissa_bits;
        if CXX_IF_CONSTEXPR (!has_implicit_leading_bit) {
            nibble_offset -= 4;
        }
        while (effective_mantissa != 0) {
            nibble_offset -= 4;
            const auto nibble = unsigned(effective_mantissa >> nibble_offset);
            CHARCONV_ASSERT(nibble < 16);
            *first++ = "0123456789abcdef"[nibble];
            ++written_hexits;
            effective_mantissa &= ~(mantissa_t{0b1111} << nibble_offset);
        }
        CHARCONV_ASSERT(nibble_offset >= 0);
        CHARCONV_ASSERT(written_hexits <= effective_precision);
        if (int remaining_hexits = effective_precision - written_hexits) {
            std::memset(first, '0', remaining_hexits);
            first += remaining_hexits;
        }
    }

    if (excess_precision > 0) {
        std::memset(first, '0', excess_precision);
        first += excess_precision;
    }

    *first++ = 'p';
    if (written_exponent >= 0) {
        *first++ = '+';
    }
    const to_chars_result result = to_chars(first, last, written_exponent);
    CHARCONV_ASSERT(result.ec == std::errc{} && result.ptr == expected_output_end);
    return result;
}

template<typename T>
to_chars_result floating_to_chars_shortest(char* first, char* const last, const T value, chars_format fmt)
{
    if (fmt == chars_format::hex) {
        return floating_to_chars_hex(first, last, value, 0);
    }

    CHARCONV_ASSERT(fmt == chars_format::fixed
            || fmt == chars_format::scientific
            || fmt == chars_format::general
            || fmt == chars_format{});

    to_chars_result result_tmp = handle_special_value(first, last, value, fmt, 0);
    if (result_tmp.ptr != nullptr) {
        return result_tmp;
    }

    // TODO : gcc/libstdc++-v3/src/c++17/floating_to_chars.cc:1123 - __floating_to_chars_shortest()
}

template<typename T>
to_chars_result floating_to_chars_precision(char* first, const char* last, const T value, 
    chars_format fmt, const int precision)
{
    return to_chars_result();
}

} // namespace detail


to_chars_result to_chars(char* first, char* last, float value)
{
    return detail::floating_to_chars_shortest(first, last, value, chars_format{});
}

to_chars_result to_chars(char* first, char* last, double value)
{
    return detail::floating_to_chars_shortest(first, last, value, chars_format{});
}

to_chars_result to_chars(char* first, char* last, long double value)
{
    return detail::floating_to_chars_shortest(first, last, static_cast<double>(value), chars_format{});
}

to_chars_result to_chars(char* first, char* last, float value, chars_format fmt)
{
    return detail::floating_to_chars_shortest(first, last, value, fmt);
}

to_chars_result to_chars(char* first, char* last, double value, chars_format fmt)
{
    return detail::floating_to_chars_shortest(first, last, value, fmt);
}

to_chars_result to_chars(char* first, char* last, long double value, chars_format fmt)
{
    return detail::floating_to_chars_shortest(first, last, static_cast<double>(value), fmt);
}

to_chars_result to_chars(char* first, char* last, float value, chars_format fmt, int precision)
{
    return detail::floating_to_chars_precision(first, last, value, fmt, precision);
}

to_chars_result to_chars(char* first, char* last, double value, chars_format fmt, int precision)
{
    return detail::floating_to_chars_precision(first, last, value, fmt, precision);
}

to_chars_result to_chars(char* first, char* last, long double value, chars_format fmt, int precision)
{
    return detail::floating_to_chars_precision(first, last, static_cast<double>(value), fmt, precision);
}